Memperkuat dasar-dasar Daftar Berkaitan dengan mendefinisikan struktur Node dan menganalisis efisiensi operasi pointer inti.
- Perbedaan struktural yang baru saja kita amati—terutama penggunaan pointer dinamis—membuat Daftar Berkaitan menjadi alat yang kuat untuk aplikasi tertentu di mana penyisipan dan penghapusan sering dilakukan. Sebelum mempelajari algoritma yang kompleks, kita harus terlebih dahulu membangun fondasi yang kuat dalam definisi dan mekanika inti struktur ini.
- Bagian kuliah ini didedikasikan untuk menguasai Daftar Berkaitan. Rencana perjalanan kami akan membimbing kita melalui konsep-konsep dasarnya serta penerapannya secara praktis pada masalah struktur data klasik:
- Tujuan:Pahami mengapa Daftar Berkaitan dipilih ketika ukuran $n$ bersifat tidak stabil atau tidak diketahui, dan efisiensi bergantung pada penghubungan ulang pointerdaripada pergeseran memori.
- Gambaran Rencana Perjalanan:
- 1. Struktur & Definisi:Kami akan secara formal mendefinisikan Struktur_Node (data dan pointer $next$) serta membandingkan perbedaan antara Daftar Berkaitan Tunggal, Ganda, dan Melingkar.
- 2. Operasi Inti:Menguasai manipulasi pointer:
- Traversal: Mengiterasi daftar, membutuhkan waktu $O(n)$.
- Penyisipan: Menambahkan node pada posisi $i$ yang diketahui, yang dapat dilakukan secara efisien dalam waktu $O(1)$ dengan menyesuaikan pointer $next$ menggunakan Warna_Penghubungan_Ulang_Pointer.
- Penghapusan: Menghapus node dan menyesuaikan pointer, juga $O(1)$.
- 3. Aplikasi Ilustratif (Polinomial):Kami akan menggunakan Daftar Berkaitan untuk menyimpan dan memanipulasi polinomial aljabar, di mana setiap node menyimpan Term_Polinomial ($\langle koefisien, pangkat \rangle$). Ini menunjukkan bagaimana Daftar Berkaitan unggul dalam manajemen struktur dinamis, khususnya untuk penjumlahan polinomial, yang sering berjalan dalam waktu $O(n+m)$.
Kompleksitas Operasi Inti Daftar Berkaitan
| Operasi | Deskripsi | Kompleksitas |
|---|---|---|
| Traversal | Mencari elemen atau akhir daftar. | $O(n)$ |
| Penyisipan (pada posisi $i$ yang diketahui) | Menyesuaikan dua pointer. | $O(1)$ |
| Penghapusan (pada posisi $i$ yang diketahui) | Menyesuaikan satu pointer. | $O(1)$ |